/**
 * 
 */
package ro.dta.idbi.model.dynamicpattern;

import ro.dta.idbi.interfaces.IDistMatrixCalculator;

/**
 * Implementation of the Floyd Warshall algorithm for distance matrix
 * computation
 * 
 * @author Tudor Dobrila
 * 
 */
public class FloydWarshall implements IDistMatrixCalculator {

	@Override
	public double[][] calculateDistanceMatrix(int[][] graph) {
		int noVertices = graph.length;
		int noCols = graph[0].length;

		if (noVertices != noCols) {
			throw new IllegalArgumentException("Expected a squared adjancecy matrix.");
		}

		double[][] result = new double[noVertices][];
		for (int i = 0; i < noVertices; i++) {
			result[i] = new double[noVertices];
		}

		for (int i = 0; i < noVertices; i++) {
			for (int j = 0; j < noVertices; j++) {
				if (i == j || graph[i][j] != 0) {
					result[i][j] = graph[i][j];
				} else {
					result[i][j] = Double.POSITIVE_INFINITY;
				}
			}
		}

		for (int k = 0; k < noVertices; k++) {
			for (int i = 0; i < noVertices; i++) {
				for (int j = 0; j < noVertices; j++) {
					result[i][j] = Math.min(result[i][j], result[i][k] + result[k][j]);
				}
			}
		}

		return result;
	}
}
